/*
 * @Author: kaikaima
 * @Date: 2020-12-09 13:24:21
 * @LastEditTime: 2020-12-16 15:00:24
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: /undefined/home/messi/Data_Structure_and_Algorithm_GIT/Hash/Hashing.h
 */
#ifndef __hhxxttxs_hashing__
#define __hhxxttxs_hashing__

#include <iostream>
#include <string>

/**
 * @description: noA is the 70th prime number and means the factor of hashing function
 * @description: noB is the 448th prime number and means the size of the hash-table
 * @description: 
 */
const int noA = 349;
const int noB = 3167;
#define outputnum 20

class hashtable{
    private:
    class element
    {
    /**
     * @description: data is the string
     * @description: num is the number of collision for the same data
     * @description: next is to solve collisions for different datas by chaining
    */  
    public:
    std::string data;
    int num;
    element* next;
    element() {num=0;next=NULL;};
    element(std::string _data) {data=_data;num=1;next=NULL;};
    };
    /**
     * @description: table is the hash_table
    */
    element* table[noB]={NULL};
    void insert(std::string _data, element **_space);
    void release(element* _p);
    int min(int *_arr);
    public:
    hashtable() {};
    hashtable(std::string _data);
    ~hashtable();
    void input();
    void output() const;
    void output_20();
    void search(std::string _data) const;
};

void hashtable::release(element* _p){
    while(_p!=NULL){
        release(_p->next);
    }
    delete _p;
};

/**
 * @description: min is to return the minimum element in the given array of (outputnum) integers
 * @param {*} address of an array of (outputnum) integers
 * @return {*} the subscript of the minimum element
 */
int hashtable::min(int *_arr){
    int key=0;
    for(int i=1;i<outputnum;i++){
        if(_arr[key]>_arr[i])
        key=i;
        if(_arr[key]==0)
        break;
    }
    return key;
};

hashtable::hashtable(std::string _data){
    insert(_data, table);
};

hashtable::~hashtable(){
    for(int i=0;i<noB;i++){
        element *p=table[i];
        while(p!=NULL){
            release(p);
        }
    }
};

/**
 * @description: insert is an intrinsic function to add a string to the hash_table
 * @param {*} a string to be inserted; a piece of space in hash_table
 * @return {*} nothing
 */
void hashtable::insert(std::string _data, element **_space){
    /**
     * @description: if there is no collision(this piece of space is NULL), set a new element and settle down here
     */
    if(*_space==NULL){
        element *p=new element (_data);
        *_space=p;
    }
    /**
     * @description: if they are the same(collision happened), num++ and do not insert it again
     */
    else if((*_space)->data==_data){
        ((*_space)->num)++;
    }
    /**
     * @description: if a collision happened but their datas are not eqaul, turn to the next
     */
    else
    {
        (*_space)=(*_space)->next;
        insert(_data, _space);
    }   
};

/**
 * @description: input is an external function and will be executed until your active stop
 * @param {*} no matter what you typed
 * @return {*} nothing
 */
void hashtable::input(){
    /**
     * @description: p is the string that will be inserted while _p is what you typed
     * @description: hashkey's initial value is 0
     */
    std::string p;
    unsigned int hashkey=0;
    char _p;
    while(_p=std::cin.get()){
        /**
         * @description: if _p is a capital, turn it to its lower case
         * @description: hashkey is not case sensitive
         */
        if(_p>='A'&&_p<='Z'){
            hashkey=((hashkey)*noA+int(_p)-64)%noB;
            p+=_p+'a'-'A';
        }
        else if(_p>='a'&&_p<='z'){
            hashkey=((hashkey)*noA+int(_p)-96)%noB;
            p+=_p;
        }
        /**
         * @description: abbreviation form will be considered as independent words (like we're);
         * @description: link break will not be considered (like in-dependent)
         * @description: other symbols will be seen as the end of word; p and hashkey will be initialized
         * @description: if you typed an independent word "endformk", this input will stop
         */
        else if(_p=='\'')
            p+=_p;
        else{
            if(_p=='-'||p.size()==0)
            continue;
            else{
                if(p=="endformk")
                return;
                insert(p, table+(hashkey)%noB);
                hashkey=0;
                p="";
            }
        }
    }
};

/**
 * @description: output is a const external function
 * @param {*} nothing
 * @return {*} output all the strings with its frequency misorderly
 */
void hashtable::output() const{
    for(int i=0;i<noB;i++){
        element *p=table[i];
        while(p!=NULL){
            std::cout<<p->data<<"\t"<<p->num<<std::endl;
            p=p->next;
        }
    }
};

/**
 * @description: output_20 isn external function
 * @param {*} nothing
 * @return {*} output the top (outputnum) frequency of the strings in hash_table misorderly
 */
void hashtable::output_20(){
    std::string n1[outputnum];
    int n2[outputnum]={0};
    for (int i=0;i<noB;i++){
        element *p=table[i];
        while(p!=NULL){
            int m=hashtable::min(n2);
            /**
             * @description: always change the minimum one so that this is an out of order output
             */
            if(p->num>n2[m]){
                n2[m]=p->num;
                n1[m]=p->data;
            }
            p=p->next;
        }
    }
    for(int i=0;i<outputnum;i++){
        if(n2[i]!=0)
        std::cout<<n1[i]<<"\t"<<n2[i]<<std::endl;
        else
        break;
    }
};

/**
 * @description: search is a const external function
 * @param {*} a string
 * @return {*} output the string with its frequency if it is in the hash_table; if not, output "can not find it"
 */
void hashtable::search(std::string _data) const{
    int hashkey=0;
    for(std::string::iterator it=_data.begin();it!=_data.end();it++){
        char p=*it;
        if(p>='A'&&p<='Z'){
            hashkey=(hashkey)*noA+int(p)-64;
        }
        else if(p>='a'&&p<='z'){
            hashkey=(hashkey)*noA+int(p)-96;
        }
        else if(p=='\'')
            p+=p;
        else continue;
    }
    element* key=table[(hashkey)%noB];
    while(key!=NULL){
        if(key->data==_data){
            std::cout<<_data<<"\t"<<key->num<<std::endl;
            return;
        }
        else
        key=key->next;
    }
    std::cout<<"can not find it"<<std::endl;
};

#else
//do nothing
#endif